import java.util.PriorityQueue;

/**
 *
 * 给你一个n x n矩阵matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
 * 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
 * 你必须找到一个内存复杂度优于O(n2) 的解决方案。
 * */
public class LeetCode378 {
    /**
     *关键思路：如何找到矩阵中当前的最小值，弹出，第k个弹出的元素就是第k小的元素，那么如何找到当前矩阵中的最小值了，因为矩阵列和行都是升序排列的，
     * 第一列在每行都是最小值，那么最小值肯定在第一列中产生，其实就是左上角的数字。那么将左上角的数字弹出后，如何确定下一个候选数字了，就是把弹出的数字的右边的数字加进去
     * 这里我们使用堆这种数据结构。
     */
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        //存放矩阵元素下标的小顶堆
        PriorityQueue<int[]> minsHeap = new PriorityQueue<>((pair1, pair2) -> {
            return matrix[pair1[0]][pair1[1]] - matrix[pair2[0]][pair2[1]];
        });
        //将第一列的下标加入堆中
        for (int i = 0; i < n; i++) {
            minsHeap.add(new int[]{i, 0});
        }
        int res = 0;
        for (int i = 0; i < k; i++) {
            int[] pair = minsHeap.poll();
            res = matrix[pair[0]][pair[1]];
            if (pair[1] + 1 < n) {
                minsHeap.add(new int[]{pair[0], pair[1] + 1});
            }
        }
        return res;
    }
}
